#include<vector>
using namespace std;
class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        // 用最长子序列长度作为改数组的下标索引

        vector<int> arr;
        arr.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            // 如果此时当前值大于我们数组的最后一个的值说明要添加一个值
            int num = nums[i];
            if (num > arr.back())
                arr.push_back(num);
            else
            {
                // 用2分去找该数字应该的位置
                // 就是第一个大于等于num的下标
                int l = 0, r = arr.size() - 1, ans = -1;
                while (l <= r)
                {
                    auto check = [&arr](int mid, int num) -> bool
                    {
                        if (arr[mid] >= num)
                            return true;
                        return false;
                    };
                    int mid = (r - l) / 2 + l;
                    if (check(mid, num))
                    {
                        ans = mid;
                        r = mid - 1;
                    }
                    else
                    {
                        l = mid + 1;
                    }
                }
                arr[ans] = num;
            }
        }
        return arr.size();
    }
};